package leetcode.code1224;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution3 implements IDebug {

	int MAX = (int) 1e5 + 1;

	public int maxEqualFreq(int[] nums) {
		int[] cnt = new int[MAX], sum = new int[MAX];
		int n = nums.length, max = 0, ans = 0;
		for (int i = 0; i < n; i++) {
			int t = nums[i], cur = ++cnt[t], len = i + 1;
			sum[cur]++;
			sum[cur - 1]--;
			max = Math.max(max, cur);
			if (max == 1)
				ans = len;
			else if (max * sum[max] + 1 == len)
				ans = len;
			else if ((max - 1) * (sum[max - 1] + 1) + 1 == len)
				ans = len;
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(2, this.maxEqualFreq(H.str2array3("[1,1]")));
		H.compare(25, this.maxEqualFreq(H.str2array3(
				"[1,1,1,2,2,2,3,3,3,4,4,4,5,1,1,1,2,2,2,3,3,3,4,4,4,5,1,1,1,2,2,2,3,3,3,4,4,4,5,1,1,1,2,2,2,3,3,3,4,4,4,5]")));
		H.compare(13, this.maxEqualFreq(H.str2array3("[2,2,1,1,5,3,3,5,2,1,1,5,3,3,2]")));
		H.compare(5, this.maxEqualFreq(H.str2array3("[1,2,7,3,3,3,4,4,4,4]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
